package com.suanfa;


import com.hanhai.CalenderDemo;

import java.net.Inet4Address;
import java.util.Arrays;
import java.util.concurrent.TimeUnit;

/**
 * 快速排序
 *
 * @Author weijingchen
 * @Date 2025/6/2 22:09
 * @Version 1.0.0
 */
public class Test13 {
    public static void main(String[] args) {


        int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        int i = 0;
        int j = arr.length - 1;
        quickSort(arr, i, j);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort(int[] arr, int i, int j) {
        // 定义两个变量记录要查找的范围
        int start = i;
        int end = j;
        if (start >= end) {
            return;
        }
        // 记录基准数
        int baseNumber = arr[i];
        while (start != end) {
            //利用end，从后往前开始找，找比基准数小的数字
            while (true) {
                if (end <= start || arr[end] < baseNumber) {
                    break;
                }
                end--;
            }

            //利用start，从前往后开始找，找比基准数大的数字
            while (true) {
                if (end <= start || arr[start] > baseNumber) {
                    break;
                }
                start++;
            }
            //把end和start位置的数字交换
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
        // 当start和end相等时，交换位置的数字
        //把start位置的数字和基准数交换
        //基准数归位
        int temp = arr[i];
        arr[i] = arr[start];
        arr[start] = temp;
        // 递归调用
        //  对start左边的数组进行排序
        quickSort(arr, i, start - 1);
        // 对start右边的数组进行排序
        quickSort(arr, start + 1, j);
    }
}
